package com.mgq.algorithm;

import java.util.ArrayList;
import java.util.List;

/**
 * @author maguangqi
 * @version 1.0
 * https://leetcode-cn.com/problems/generate-parentheses/
 * 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
 * <p>
 * 输入：n = 3
 * 输出：[
 * "((()))",
 * "(()())",
 * "(())()",
 * "()(())",
 * "()()()"
 * ]
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/generate-parentheses
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @date 2020/7/14 22:30
 */
public class Parenthesis22 {
    /**
     * 方法一: 使用暴力解法,递归, 总共有n对括号,也就是说总共是2n个字符
     * 最终的结果是2的2n次方 2^2n
     */
    public List<String> generateParenthesis(int n) {
        List<String> combinations = new ArrayList();
        generateAll(new char[2 * n], 0, combinations);
        return combinations;
    }

  /**
   * description: 时间复杂度o(2^2n*n)
   * create time: 2020/7/15 0:02
    * @param current 当前数组的长度
    * @param pos  表示在数组中当前的位置
    * @param result 符合条件的结果
   * @return void
   *  null null null null null null
   *
   *只考虑单次的过程,只要n固定下来,那么最终的结果就是一个2n的数组,因为2对括号
   * 那么每次先把左括号加进去,接着位置pos+1,然后一位,然后把右括号加进去,接着位置pos+1
   * 终止条件是pos=当前数组的长度2n时.表示已经填满了,那么只需要验证填满的数组是否满足条件即可
   */
    public void generateAll(char[] current, int pos, List<String> result) {
        //终止条件是当前的位置等于数组的长度,也就是数组放满了
        if (pos == current.length) {
            if (valid(current))
                result.add(new String(current));
        } else {
            //每一步不是加左括号就是加右括号
            current[pos] = '('; //先加左括号
            //把位置加1
            //左括号加完了,把pos+1,位置向后移动
            generateAll(current, pos + 1, result);
            //放右括号
            current[pos] = ')';
            //把位置加1
            generateAll(current, pos + 1, result);
        }
    }

    public boolean valid(char[] current) {
        System.out.println(new String(current));
        int balance = 0;
        for (char c : current) {
            if (c == '(') {
                balance++;
            } else {
                balance--;
            }
            //去掉第一个是右括号的情况,也就是说第一个是右括号时,balance就已经小于0了,直接return
            //这样就避免了)(这种情况
            if (balance < 0) {
                return false;
            }
        }
        return (balance == 0);
    }
    /**
     * description: 解法二: 使用回溯的方法,剪枝
     * create time: 2020/7/15 22:45
      * @param n 括号的对数
     * @return
     */
    public List<String> generateParenthesis2(int n) {
        List<String> result = new ArrayList<>();
        generateAll2(0, 0, n, result, "");
        return result;
    }
    /**
     * description: 方法二: 使用剪枝的方法,将不符合的部分剪掉
     * create time: 2020/7/15 23:18
      * @param left 已经使用左括号的个数
      * @param right 已经使用右括号的个数
      * @param n 总的括号的对数(比如3,表示3对括号)
      * @param result 总结果
      * @param current 当前结果
     * @return
     */
    public void generateAll2(int left, int right, int n, List<String> result, String current) {
        if (left == n && right == n) {
            //表示满足2n的条件了.将当前结果放入到result中
            result.add(current.toString());
            return;
        }
        if (left < n) {
            //如果左括号还没有用完,把左括号加到当前字符串中
            //用了一个,那么left+1
            generateAll2(left+1,right,n,result, current+"(");
        }
        //right<n,表示右括号没有用完, left>right 表示已经使用的左括号个数大于已经使用的右括号的个数
        //因为只有这样才有意义.比如已经用了3个左括号,2个右括号,才有可能再使用右括号.
        //如果已经用了2个左括号,3个右括号,这种再使用右括号没有意义了.这就是某种意义上的剪枝
        if (right < n && left > right) {
            generateAll2(left,right+1,n,result,current+")");
        }
    }
    public static void main(String[] args) {
        Parenthesis22 parenthesis22 = new Parenthesis22();
        List<String> strings = parenthesis22.generateParenthesis(1);
        System.out.println("-----------方法一--------------");
        strings.forEach(System.out::println);
        parenthesis22.generateParenthesis(2);
        System.out.println("-------方法二------------------");
        //   parenthesis22.generateParenthesis(3);
        List<String> result = parenthesis22.generateParenthesis2(2);
        result.forEach(System.out::println);
    }
}
